"""
Jeu de Röckse - Fonctions de base
Ce fichier contient toutes les fonctions des parties I, II et III du sujet,
ainsi que les fonctions auxiliaires nécessaires pour la partie IV (programmation dynamique).
"""

import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import numpy as np

# Constante globale
INFINI = 10**15

# ==============================================================================
# PARTIE I : Sauts et chemins
# ==============================================================================
def poids(T, chemin):
    """
    Calcule le poids (somme des pénalités) d'un chemin.
    
    Paramètres:
        T : grille de jeu (liste de listes d'entiers)
        chemin : liste de cases (i, j)
    
    Retourne:
        Le poids total du chemin (entier)
    """
    total = 0
    for (i, j) in chemin:
        total += T[i][j]
    return total

def appliquer_sauts(i, j, sauts):
    """
    Applique une liste de sauts à partir d'une case donnée.
    
    Paramètres:
        i, j : coordonnées de la case de départ
        sauts : liste de sauts (delta_i, delta_j)
    
    Retourne:
        La case (i_final, j_final) atteinte après avoir appliqué tous les sauts
    """
    for (delta_i, delta_j) in sauts:
        i += delta_i
        j += delta_j
    return (i, j)

def sauts_corrects(sauts_defaut, bonus, chemin):
    """
    Vérifie si les sauts utilisés dans un chemin sont corrects.
    
    Paramètres:
        sauts_defaut : liste des sauts autorisés par défaut
        bonus : dictionnaire des cases bonus et leurs sauts associés
        chemin : liste de cases formant le chemin
    
    Retourne:
        True si tous les sauts sont corrects, False sinon
    """
    if len(chemin) <= 1:
        return True
    
    sauts_disponibles = sauts_defaut[:]
    
    for k in range(len(chemin) - 1):
        (i, j) = chemin[k]
        
        # Activer les bonus si on est sur une case bonus (AVANT de vérifier le saut)
        if (i, j) in bonus:
            for saut_bonus in bonus[(i, j)]:
                if saut_bonus not in sauts_disponibles:
                    sauts_disponibles.append(saut_bonus)
        
        (i_suiv, j_suiv) = chemin[k + 1]
        delta = (i_suiv - i, j_suiv - j)
        
        if delta not in sauts_disponibles:
            return False
    
    return True

def sauts_bien_formes(sauts_defaut, bonus):
    """
    Vérifie que tous les sauts satisfont la condition (*) : strictement positifs
    lexicographiquement, ce qui garantit l'absence de cycles.
    
    Paramètres:
        sauts_defaut : liste des sauts par défaut
        bonus : dictionnaire des cases bonus et leurs sauts associés
    
    Retourne:
        True si tous les sauts sont bien formés, False sinon
    """
    def est_positif_lexico(delta_i, delta_j):
        return delta_i > 0 or (delta_i == 0 and delta_j > 0)
    
    for (delta_i, delta_j) in sauts_defaut:
        if not est_positif_lexico(delta_i, delta_j):
            return False
    
    for case_bonus in bonus:
        for (delta_i, delta_j) in bonus[case_bonus]:
            if not est_positif_lexico(delta_i, delta_j):
                return False
    
    return True


# ==============================================================================
# PARTIE II : Recherche exhaustive
# ==============================================================================
def trouve_complet(T, sauts_defaut, bonus, sauts_max, i=0, j=0):
    """
    Trouve un chemin de poids minimum avec au plus sauts_max sauts.
    Le chemin ne mène pas forcément à l'arrivée.
    Paramètres:
        T : grille de jeu
        sauts_defaut : liste des sauts par défaut
        bonus : dictionnaire des cases bonus
        sauts_max : horizon de recherche (nombre max de sauts)
    Retourne:
        (poids_min, liste_sauts) où poids_min est le poids minimal et liste_sauts
        la liste des sauts pour atteindre ce poids. Retourne INFINI si aucun chemin
        n'est trouvé vers l'arrivée.
    """
    N = len(T)

    def trouve_complet_rec(i, j, horizon, sauts_disponibles):
        if (i, j) in bonus:
            for saut_bonus in bonus[(i, j)]:
                if saut_bonus not in sauts_disponibles:
                    sauts_disponibles = sauts_disponibles + [saut_bonus]

        # Cas de base : arrivée atteinte
        if i == N-1 and j == N-1:
            return (T[i][j], [])

        # Cas de base : horizon épuisé
        if horizon == 0:
            return (T[i][j], [])

        # On DOIT continuer si un saut est possible
        meilleur_poids = INFINI
        meilleurs_sauts = []

        for (delta_i, delta_j) in sauts_disponibles:
            i_dest = i + delta_i
            j_dest = j + delta_j

            if 0 <= i_dest < N and 0 <= j_dest < N:
                (poids_dest, sauts_dest) = trouve_complet_rec(
                    i_dest, j_dest, horizon - 1, sauts_disponibles[:])

                poids_total = T[i][j] + poids_dest
                if poids_total < meilleur_poids:
                    meilleur_poids = poids_total
                    meilleurs_sauts = [(delta_i, delta_j)] + sauts_dest

        # Si aucun saut valide, on est bloqué ici
        if meilleur_poids == INFINI:
            return (T[i][j], [])

        return (meilleur_poids, meilleurs_sauts)

    return trouve_complet_rec(i, j, sauts_max, sauts_defaut[:])

def trouve_complet_memo(T, sauts_defaut, bonus, sauts_max, dico_memo, i=0, j=0):
    """
    Trouve un chemin de poids minimum avec au plus sauts_max sauts.
    Version avec mémoïsation.
    
    Paramètres:
        T : grille de jeu
        sauts_defaut : liste des sauts par défaut
        bonus : dictionnaire des cases bonus
        sauts_max : horizon de recherche
        dico_memo : dictionnaire pour la mémoïsation (initialement {})
    """
    N = len(T)

    def trouve_complet_rec(i, j, horizon, sauts_disponibles):
        # Clé de mémoïsation : (position, horizon, ensemble des sauts)
        cle = (i, j, tuple(sauts_disponibles))

        if (i, j) in bonus:
            for saut_bonus in bonus[(i, j)]:
                if saut_bonus not in sauts_disponibles:
                    sauts_disponibles = sauts_disponibles + [saut_bonus]

        # Cas de base : arrivée atteinte
        if i == N-1 and j == N-1:
            dico_memo[cle] = (T[i][j], [])
            return (T[i][j], [])

        # Cas de base : horizon épuisé
        if horizon == 0:
            dico_memo[cle] = (T[i][j], [])
            return (T[i][j], [])

        # On DOIT continuer si un saut est possible
        meilleur_poids = INFINI
        meilleurs_sauts = []

        for (delta_i, delta_j) in sauts_disponibles:
            i_dest = i + delta_i
            j_dest = j + delta_j

            if 0 <= i_dest < N and 0 <= j_dest < N:
                (poids_dest, sauts_dest) = trouve_complet_rec(
                    i_dest, j_dest, horizon - 1, sauts_disponibles[:])

                poids_total = T[i][j] + poids_dest
                if poids_total < meilleur_poids:
                    meilleur_poids = poids_total
                    meilleurs_sauts = [(delta_i, delta_j)] + sauts_dest

        # Si aucun saut valide, on est bloqué ici
        if meilleur_poids == INFINI:
            dico_memo[cle] = (T[i][j], [])
            return (T[i][j], [])

        dico_memo[cle] = (meilleur_poids, meilleurs_sauts)
        return (meilleur_poids, meilleurs_sauts)

    return trouve_complet_rec(i, j, sauts_max, sauts_defaut[:])


# ==============================================================================
# FONCTIONS AUXILIAIRES POUR LA PARTIE IV
# ==============================================================================
def ranger_bonus(bonus):
    """
    Organise les cases bonus pour faciliter leur manipulation.
    
    Paramètres:
        bonus : dictionnaire {(i,j): [liste de sauts]}
    
    Retourne:
        (bonus_au_rang, rang_du_bonus) où :
        - bonus_au_rang[k] est la liste des sauts activés par la case bonus k
        - rang_du_bonus[(i,j)] est le numéro de la case bonus (i,j)
    """
    bonus_au_rang = []
    rang_du_bonus = {}
    
    k = 0
    for (i, j) in bonus:
        bonus_au_rang.append(bonus[(i, j)])
        rang_du_bonus[(i, j)] = k
        k += 1
    
    return (bonus_au_rang, rang_du_bonus)

def code_bonuslib(masque_bonus):
    code = 0
    for i in range(len(masque_bonus)):
        code = code + masque_bonus[i]*2**i
    return code

def ajouter_bonus(bonus,rang_du_bonus,i,j,bonus_actifs,code_bonus_actifs):
    """
    Fonction ajouter_bonus
    Exemple : si bonus = {(1, 2): [(1, 0),(-1,0)], (1,3):[(-1,-1)]} (rang k = 0 et 1)
              rang_du_bonus = {(1, 2): 0, (1, 3): 1}
              bonus_actifs = [False, False] <=> code_bonus_actif = 0
              (i,j) = (1,3)
              => Il faut activer le bonus de la case (1,3), c'est-à-dire k=1
              => il faut retourner bonus_actifs => [False,True]
    """

    # Si (i,j) n'est pas une case bonus
    # renvoi code_bonus_actifs (aucun changement)
    if (i,j) not in bonus:
        return code_bonus_actifs

    # Sinon, récupère le rang du bonus
    k = rang_du_bonus[(i,j)]

    # Active le bonus du rang k dans le masque
    bonus_actifs[k] = True

    # Retourne le code_bonus associé au masque
    return code_bonuslib(bonus_actifs)